//
//  Problem41.swift
//  TestProject 41. 缺失的第一个正数
//
//  Created by 武侠 on 2020/8/25.
//  Copyright © 2020 zhulong. All rights reserved.
//

import UIKit

/*
 41. 缺失的第一个正数
 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

 示例 1:  输入: [1,2,0]         输出: 3
 示例 2:  输入: [3,4,-1,1]      输出: 2
 示例 3:  输入: [7,8,9,11,12]   输出: 1
 提示：
 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
 */
@objcMembers class Problem41: NSObject {
    func solution() {
        print(firstMissingPositive([1,2,0]))
        print(firstMissingPositive([3,4,-1,1]))
        print(firstMissingPositive([7,8,9,11,12]))
    }
    
    // 思路：
    // 将value，放到对应的位置 i+1的位置
    // 然后，重新遍历，发现value != i+1 就是i+1
    func firstMissingPositive(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 1
        }
    
        var numList = nums
        for i in 0..<numList.count {
            if (i + 1) != numList[i] {
                while numList[i] > 0 && numList[i] <= numList.count && numList[numList[i] - 1] != numList[i] {
                        let temp = numList[i]
                        numList[i] = numList[numList[i] - 1]
                        numList[temp - 1] = temp
                }
            }
        }
        
        for i in 0..<numList.count {
            if (i + 1) != numList[i] {
                return i + 1
            }
        }
        return numList.count + 1
    }
}
